#pragma once

#include <iostream>

template<typename T>
class LinkList
{
public:
	struct Node
	{
		Node():data(),next(nullptr)
		{};

		Node(T inData):data(inData),next(nullptr)
		{};
		
		T data;
		Node* next;
	};
	
	LinkList();
	~LinkList();

	void ShowData();
	int Size() const;

	/**
	 * 末端插入
	 * @param element 
	 */
	void Insert(T element);

	/**
	 * 指定位置插入
	 * @param index 
	 * @param element 
	 */
	void Insert(int index, T element);
	
	void Remove(int index);
	T operator[](int index);

	/**
	 * 反转链表
	 */
	void Reverse();

	// 搜索元素，返回元素节点
	Node* Find(const T& element);

	// 链表排序
	void Order(bool isIncreasing=true);

	Node* GetHead(){return head;};
private:
	int size;
	Node* head;
};

template <typename T>
LinkList<T>::LinkList():
	size(0),
	head(nullptr)
{
}

template <typename T>
LinkList<T>::~LinkList()
{
	Node* deletedNode = nullptr;
	Node* temp = head;
	while (temp)
	{
		deletedNode = temp;
		temp = temp->next;
		delete deletedNode;
	}
}

template <typename T>
void LinkList<T>::ShowData()
{
	std::cout << "Show LinkList: \n";
	std::cout << "Size: " << size << "\n";

	Node* temp = head;
	if (temp)
	{
		std::cout << temp->data;
		temp = temp->next;
	}
	
	while (temp)
	{
		std::cout << " -> " << temp->data;
		temp = temp->next;
	}
	std::cout << std::endl;
}

template <typename T>
int LinkList<T>::Size() const
{
	return size;
}

template <typename T>
void LinkList<T>::Insert(T element)
{
	if (head)
	{
		// 如果 head 不为空

		Node* temp = head;
		// 如果 next 为空，说明temp是末端节点
		while (temp->next)
			temp = temp->next;

		temp->next = new Node(element);
	}
	else
	{
		// 如果 head 为空
		
		head = new Node(element);
	}

	++size;
}

template <typename T>
void LinkList<T>::Insert(int index, T element)
{
	if (index < 0 || index > size)
		return;

	if (head)
	{
		// 如果 head 不为空
		Node* temp = head;
		if (index == 0)
		{
			head = new Node(element);
			head->next = temp;
		}
		else if (index == 1)
		{
			temp = temp->next;
			head->next = new Node(element);
			head->next->next = temp;
		}
		else
		{
			// 找到对应索引的前驱节点
			for (int i = 0; i < index - 1; ++i)
				temp = temp->next;

			Node* newNode = new Node(element);
			newNode->next = temp->next;
			temp->next = newNode;
		}

		++size;
	}
	else
	{
		// 如果 head 为空，插入 head 末端
		Insert(element);
	}
}

template <typename T>
void LinkList<T>::Remove(int index)
{
	if (index < 0 || index >= size)
		return;
	
	Node* deletedNode = head;
	if (index == 0)
	{
		head = head->next;
	}
	else if (index == 1)
	{
		deletedNode = head->next;
		head->next = head->next->next;
	}
	else
	{
		Node* temp = head;
		// 找到对应索引的前驱节点
		for (int i = 0; i < index - 1; ++i)
			temp = temp->next;

		deletedNode = temp->next;
		temp->next = temp->next->next;
	}

	delete deletedNode;
	--size;
}

template <typename T>
T LinkList<T>::operator[](int index)
{
	Node* temp = head;
	for (int i = 0; i < index; ++i)
		temp = temp->next;

	return temp->data;
}

template <typename T>
void LinkList<T>::Reverse()
{
	if (size < 2)
		return;

	Node *prev, *current, *next;
	prev = nullptr;
	current = head;
	while (current)
	{
		next = current->next;
		current->next = prev;
		prev = current;
		current = next;
	}
	head = prev;
}

template <typename T>
typename LinkList<T>::Node* LinkList<T>::Find(const T& element)
{
	Node* current = head;
	while(current)
	{
		if(current->data == element)
			return current;

		current = current->next;
	}

	return nullptr;
}

template <typename T>
void LinkList<T>::Order(bool isIncreasing)
{
	if(!head)
		return;

	// 待排序节点
	Node* temp = head;
	head = nullptr;
	if(isIncreasing)
	{
		// 递增排序

		while(temp)
		{
			// 待排序节点中的下一个
			Node* next = temp->next;
			// 已排序节点迭代对象
			Node* iter = head;
			// 如果头结点为空，说明已排序链表为空，直接添加
			if(head == nullptr)
			{
				head = temp;
				head->next = nullptr;
			}
			else
			{
				// 当前节点的前驱节点
				Node* prev = nullptr;
				while(iter)
				{
					// 如果待排序节点小于等于当前迭代对象
					if(temp->data <= iter->data)
					{
						// 如果 当前已排序迭代对象前驱为空，说明当前节点是第一个
						if(prev == nullptr)
						{
							Node* tempNode = head;
							head = temp;
							head->next = tempNode;
						}
						else
						{
							// 否则，将待排序节点插入到迭代对象前面
							Node* tempNode = iter;
							prev->next = temp;
							prev->next->next = tempNode;
						}
						break;
					}
					else if(iter->next == nullptr)
					{
						temp->next = nullptr;
						iter->next = temp;
						break;
					}

					prev = iter;
					iter = iter->next;
				}
			}

			// 指向下一个待排序节点
			temp = next;
		}
	}
	else
	{
		// 递减排序
	}
}
